package middle;

import java.util.Arrays;

/**
 * 编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ZeroMatrixLcci {
    /**
     * 这道题如果直接将0元素所在行和列置为全部置为0的话，那么就会扰乱后面对0元素的判断。
     * 所以我们就会想到用一个新的数组，将置0后的值放入到新的数组中
     * 这样做确实很简单，但是空间复杂度为O(n*m) 如果本题要求我们仅仅能使用O(1)的空间复杂度呢
     *
     * 如果一个元素为0，那么其所在的行与列清零。那么我们其实仅需要记录这个元素所在的行号和列号。
     * 这样做，我们仅需要声明两个数组，一个是记录行号的数组，一个是记录列号的数组。
     * 在遍历完整个数组以后，我们按照记录的行号和列号 去将对应的行 和 列 清零即可
     * 那么这样做的空间复杂度为O(n+m)
     *
     * 我们再继续优化，是否可以用原数组的第一行来记录列是否被清空，用第一列来记录 对应行是否应该被清空呢？
     * 答案是可以的。但是如果首行或者首列本身就存在0呢，如果是首行存在0，那么意味着在最后我们还需要将首行整行清0.
     * 所以我们需要先遍历首行和首列 是否出现了0，用两个变量来记录一下。
     * */
    class Solution {
        public void setZeroes(int[][] matrix) {
            boolean hasZeroForRow = false;
            boolean hasZeroForColumn = false;
            // 找出首行和首列是否包含0
            for (int i = 0; i < matrix.length; i++) {
                if(matrix[i][0] == 0){
                    hasZeroForColumn = true;
                    break;
                }
            }
            for (int i = 0; i < matrix[0].length; i++) {
                if(matrix[0][i] == 0){
                    hasZeroForRow = true;
                    break;
                }
            }
            // 将为0的元素所在的首列 和 首行置为0
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++){
                    if(matrix[i][j] == 0){
                        matrix[0][j] = 0;
                        matrix[i][0] = 0;
                    }
                }
            }
            // 将首行或首列元素为0的行或列清0
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    if(matrix[i][0] == 0 || matrix[0][j] == 0){
                        matrix[i][j] = 0;
                    }
                }
            }

            // 如果首行 或者 首列本身存在0 那么就将首行 或者首列 清0
            if(hasZeroForRow){
                Arrays.fill(matrix[0], 0);
            }

            if(hasZeroForColumn){
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][0] = 0;
                }
            }
        }
    }
}
